package middle;

/**
 * 给定一个包含n + 1 个整数的数组nums ，其数字都在[1, n]范围内（包括 1 和 n），可知至少存在一个重复的整数。
 *
 * 假设 nums 只有 一个重复的整数 ，返回这个重复的数 。
 *
 * 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。
 *
 * 链接：https://leetcode-cn.com/problems/find-the-duplicate-number
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class FindTheDuplicateNumber {
    /**
     * 不能修改数组 也不能用额外的内存。
     * 以前貌似做过类似的题目  关键字：其数字都在[1, n]范围内（包括 1 和 n）
     * 以前是通过一个萝卜一个坑的思路做的，这个时候会改变原数组，题目不允许改变。
     *
     * ------------- 快慢指针 ---------------
     * 文字写的不如人家写的好 直接贴解题方案
     *  1 3 4 2 2为例：
     * 1. 怎么找到下一个结点
     * index = n[index] 起点为0 下一个结点就是1
     *
     * 2. 怎么找到下下个
     * index = n[n[index]] 起点为0 下下个结点就是3
     *
     * https://leetcode-cn.com/problems/find-the-duplicate-number/solution/287xun-zhao-zhong-fu-shu-by-kirsche/
     * */
    class Solution {
        public int findDuplicate(int[] nums) {
            int slow = nums[0];
            int fast = nums[nums[0]];
            while(slow != fast){
                slow = nums[slow];
                fast = nums[nums[fast]];
            }
            /*
             * 这部分是找到环的入口
             */
            int pre1 = 0;
            int pre2 = slow;
            while(pre1 != pre2){
                pre1 = nums[pre1];
                pre2 = nums[pre2];
            }
            return pre1;
        }
    }
}
